#ifndef DIFF_H_
#define DIFF_H_

#include <algorithm>
#include <array>
#include <cstdlib>
#include <vector>

namespace lxj
{
// 利用二维前缀和信息迅速得到二维区域和
// 测试链接 : https://leetcode.cn/problems/range-sum-query-2d-immutable/
class NumMatrix {
    std::vector<std::vector<int>> sumMatrix;

public:
    NumMatrix(std::vector<std::vector<int>>& matrix)
    {
        sumMatrix = std::vector<std::vector<int>>(matrix.size() + 1,
                                                  std::vector<int>(matrix[0].size() + 1, 0));
        for (int i = 1; i < sumMatrix.size(); i++) {
            for (int j = 1; j < sumMatrix[i].size(); j++) {
                sumMatrix[i][j] = matrix[i - 1][j - 1];
                sumMatrix[i][j] = sumMatrix[i - 1][j] + sumMatrix[i][j - 1] -
                                  sumMatrix[i - 1][j - 1] + sumMatrix[i][j];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2)
    {
        int ans = sumMatrix[row2 + 1][col2 + 1] - sumMatrix[row2 + 1][col1] -
                  sumMatrix[row1][col2 + 1] + sumMatrix[row1][col1];
        return ans;
    }
};

// 边框为1的最大正方形
// 给你一个由若干 0 和 1 组成的二维网格 grid
// 请你找出[边界]全部由 1 组成的最大 正方形 子网格
// 并返回该子网格中的元素数量。如果不存在，则返回 0。
// 测试链接 : https://leetcode.cn/problems/largest-1-bordered-square/
inline int largest1BorderedSquare(std::vector<std::vector<int>>& grid)
{
    auto get = [&grid](int i, int j) { return (i < 0 || j < 0) ? 0 : grid[i][j]; };
    auto sum = [&grid, &get](int a, int b, int c, int d) {
        return a > c ? 0 : grid[c][d] - get(c, b - 1) - get(a - 1, d) + get(a - 1, b - 1);
    };
    int n = grid.size();
    int m = grid[0].size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            grid[i][j] += get(i, j - 1) + get(i - 1, j) - get(i - 1, j - 1);
        }
    }
    if (sum(0, 0, n - 1, m - 1) == 0) return 0;

    int ans = 1;
    for (int a = 0; a < n; a++) {
        for (int b = 0; b < m; b++) {
            for (int c = a + ans, d = b + ans, k = ans + 1; c < n && d < m; c++, d++, k++) {
                if (sum(a, b, c, d) - sum(a + 1, b + 1, c - 1, d - 1) == (k - 1) << 2) ans = k;
            }
        }
    }
    return ans * ans;
}

// 二维差分模版(洛谷)
// 测试链接 : https://www.luogu.com.cn/problem/P3397

class DiffMatrix {
    std::vector<std::vector<int>>  matrix;
    std::vector<std::vector<int>>& original_matrix;

    inline void build()
    {
        for (int i = 1; i < matrix.size(); i++) {
            for (int j = 1; j < matrix.size(); j++) {
                matrix[i][j] += matrix[i][j - 1] + matrix[i - 1][j] - matrix[i - 1][j - 1];
            }
        }
    }

    inline void clone()
    {
        for (int i = 0; i < original_matrix.size(); i++) {
            std::transform(original_matrix[i].begin(),
                           original_matrix[i].end(),
                           matrix[i + 1].begin() + 1,
                           original_matrix[i].begin(),
                           std::plus<>{});
        }
    }

    // 差分
    inline void add(int a, int b, int c, int d, int k)
    {
        matrix[a][b] += k;
        matrix[c + 1][b] -= k;
        matrix[a][d + 1] -= k;
        matrix[c + 1][d + 1] += k;
    }

    inline void clear()
    {
        for (auto& m : matrix) {
            std::fill(m.begin(), m.end(), 0);
        }
    }

public:
    DiffMatrix(std::vector<std::vector<int>>& grid) : original_matrix(grid)
    {
        int n  = original_matrix.size() + 2;
        int m  = original_matrix[0].size() + 2;
        matrix = std::vector<std::vector<int>>(n, std::vector<int>(m));
    }

    inline DiffMatrix& diffMatrix(std::vector<std::array<int, 5>>& points)
    {
        for (int i = 0; i < points.size(); i++) {
            int a = points[i][0], b = points[i][1], c = points[i][2], d = points[i][3];
            int k = points[i][4];
            add(a + 1, b + 1, c + 1, d + 1, k);
        }
        build();
        clone();
        clear();
        return *this;
    }
};

// 用邮票贴满网格图
// 给你一个 m * n 的二进制矩阵 grid
// 每个格子要么为 0 （空）要么为 1 （被占据）
// 给你邮票的尺寸为 stampHeight * stampWidth
// 我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ：
// 覆盖所有空格子，不覆盖任何被占据的格子
// 可以放入任意数目的邮票，邮票可以相互有重叠部分
// 邮票不允许旋转，邮票必须完全在矩阵内
// 如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false
// 测试链接 : https://leetcode.cn/problems/stamping-the-grid/
class PossibleToStamp {
    std::vector<std::vector<int>> sum;
    std::vector<std::vector<int>> diff;

    inline void build(std::vector<std::vector<int>>& m)
    {
        for (int i = 1; i < m.size(); i++) {
            for (int j = 1; j < m[0].size(); j++) {
                m[i][j] += m[i][j - 1] + m[i - 1][j] - m[i - 1][j - 1];
            }
        }
    }

    inline int sumRegion(int a, int b, int c, int d)
    {
        return sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1];
    }

    inline void add(std::vector<std::vector<int>>& m, int a, int b, int c, int d)
    {
        m[a][b] += 1;
        m[c + 1][b] -= 1;
        m[a][d + 1] -= 1;
        m[c + 1][d + 1] += 1;
    }

public:
    bool possibleToStamp(std::vector<std::vector<int>>& grid, int h, int w)
    {
        int n = grid.size();
        int m = grid[0].size();
        sum   = std::vector<std::vector<int>>(n + 1, std::vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            std::copy(grid[i].cbegin(), grid[i].cend(), sum[i + 1].begin() + 1);
        }
        build(sum);
        diff = std::vector<std::vector<int>>(n + 2, std::vector<int>(m + 2));
        for (int a = 1, c = a + h - 1; c <= n; a++, c++) {
            for (int b = 1, d = b + w - 1; d <= m; b++, d++) {
                if (sumRegion(a, b, c, d) == 0) {
                    add(diff, a, b, c, d);
                }
            }
        }
        build(diff);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0 && diff[i + 1][j + 1] == 0) return false;
            }
        }
        return true;
    }
};

// 最强祝福力场
// 小扣在探索丛林的过程中，无意间发现了传说中"落寞的黄金之都"
// 而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场
// 经过不断的勘测记录，小扣将所有力场的分布都记录了下来
// forceField[i] = [x,y,side]
// 表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。
// 若任意一点的 力场强度 等于覆盖该点的力场数量
// 请求出在这片地带中 力场强度 最强处的 力场强度
// 注意：力场范围的边缘同样被力场覆盖。
// 测试链接 : https://leetcode.cn/problems/xepqZ5/
class FieldOfGreatestBlessing {
    inline int sort(std::vector<long long>& coordinate)
    {
        std::sort(coordinate.begin(), coordinate.end());
        int size = 1;
        for (int i = 0; i < coordinate.size(); i++) {
            coordinate[i] != coordinate[size - 1] ? coordinate[size++] = coordinate[i] : (int)0;
        }
        return size;
    }

    inline int rank(std::vector<long long>& coordinate, long long v, int size)
    {
        int l = 0;
        int r = size - 1;
        int m, ans = 0;
        while (l <= r) {
            m = l + (r - l) / 2;
            if (coordinate[m] <= v) {
                ans = m;
                l   = m + 1;
            }
            else {
                r = m - 1;
            }
        }
        return ans + 1;
    }

    inline void add(std::vector<std::vector<long long>>& diff, int a, int b, int c, int d)
    {
        diff[a][b] += 1;
        diff[c + 1][d + 1] += 1;
        diff[a][d + 1] -= 1;
        diff[c + 1][b] -= 1;
    }

public:
    int fieldOfGreatestBlessing(std::vector<std::vector<int>>& forceField)
    {
        int                    n = forceField.size();
        std::vector<long long> xs(n << 1), ys(n << 1);
        for (int i = 0, k = 0, p = 0; i < n; i++) {
            long long x = forceField[i][0];
            long long y = forceField[i][1];
            long long r = forceField[i][2];
            xs[k++]     = x * 2 - r;
            xs[k++]     = x * 2 + r;
            ys[p++]     = y * 2 - r;
            ys[p++]     = y * 2 + r;
        }
        int                                 sizex = sort(xs);
        int                                 sizey = sort(ys);
        std::vector<std::vector<long long>> diff(sizex + 2, std::vector<long long>(sizey + 2));
        for (int i = 0, a, b, c, d; i < n; i++) {
            long long x = forceField[i][0];
            long long y = forceField[i][1];
            long long r = forceField[i][2];
            a           = rank(xs, x * 2 - r, sizex);
            b           = rank(ys, y * 2 - r, sizey);
            c           = rank(xs, x * 2 + r, sizex);
            d           = rank(ys, y * 2 + r, sizey);
            add(diff, a, b, c, d);
        }
        long long ans = 0;
        for (int i = 1; i < diff.size(); i++) {
            for (int j = 1; j < diff[0].size(); j++) {
                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1];
                ans = std::max(ans, diff[i][j]);
            }
        }
        return ans;
    }
};

}   // namespace lxj

#endif